HDOJ 1098 【数学题】Ignatius's puzzle

【题目描述】

http://acm.hdu.edu.cn/showproblem.php?pid=1098

【思路】

要求是给定k，求一个最小的a，对任意的x都能使f(x)整除65，所以f(1)=5+13+ak=18+ak，只要枚举a就可以啦，范围是0到64，因为对数m取模的话，结果是0到m-1循环的啦。查了下解题证明，即证明f(x+1)也成立。

求解思路：

f(x)=5x^13+13x^5+kax;

其中题中”f(x)|65”表示对于任意的整数x,f(x)都能被65整除.所以不难推断:f(x+1)|65也成立.

f(x+1)=5(x+1)^13+13(x+1)^5+ka(x+1),

根据二项式定理:(a+b)^n=C(n,0)a^n+C(n,1)a^(n-1)b+C(n,2)a^(n-2)b^2+…+C(n,n)b^n

得：f(x+1)=5(C(13,0)+C(13,1)x+C(13,2)x^2+…+C(13,13)x^13) +
13(C(5,0)+C(5,1)x+…+C(5,5)x^5) + ka*(x+1);

从中提取出f(x)后得：

f(x+1)=f(x)+5(C(13,0) + C(13,1)x+C(13,2)x^2+…+C(13,12)x^12) +
13(C(5,0)+C(5,1)x+…+C(5,4)x^4) + ka;

不难看出出了5C(13,0) 、13C(5,0)和ka三项以外，其他项无论x取任意整数都能被65整除,所以如果5C(13,0)
+13C(5,0)+ka(相当于18+k*a)能被65整除的话，就可以得出f(x+1)|65了。

再验证一下f(1)=5+13+ka=18+ka同样适用。

所以最终的问题就是给定一个非负整数k,使得(18+k*a)|65,输出满足此条件的最小的非负整数a。

#include<stdio.h>

int main()
{
      int k,flag;

      while (~scanf("%d",&k))
      {
            flag=1;
            for (int i=1;i<=64;i++)
            {
                  if ((18+k*i)%65==0)
                  {
                        printf("%d\n",i);
                        flag=0;
                        break;
                  }
            }
            if (flag) printf("no\n");
      }

      return 0;
}